<?php

/**
 * 之前code10_BinaryTree.php 实现了二叉树,这次换一种方式看上去更清晰
 */
class BinaryTree1 {
    public $value;
    public $left;
    public $right;
}

/**
 * 前序遍历: 根节点 ---> 左子树 ---> 右子树
 */
function preorder($root) {
    if (empty($root)) {
        return;
    }

    echo $root->value . ' ';//输出根节点
    preOrder($root->left);
    preOrder($root->right);
}

/**
 * 中序遍历: 左子树---> 根节点 ---> 右子树
 */
function inorder($root) {
    if (empty($root)) {
        return;
    }

    inorder($root->left);
    echo $root->value . ' ';//输出根节点
    inorder($root->right);
}

/**
 * 后序遍历: 左子树 ---> 右子树 ---> 根节点
 */
function tailorder($root) {
    if (empty($root)) {
        return;
    }

    tailorder($root->left);
    tailorder($root->right);
    echo $root->value . ' ';//输出根节点
}

//测试
/*
      1
     / \
    2   3
   / \   \
  4   5   6

*/

$a = new BinaryTree1();
$b = new BinaryTree1();
$c = new BinaryTree1();
$d = new BinaryTree1();
$e = new BinaryTree1();
$f = new BinaryTree1();

$a->value = '1';
$b->value = '2';
$c->value = '3';
$d->value = '4';
$e->value = '5';
$f->value = '6';

$a->left = $b;
$a->right = $c;
$b->left = $d;
$b->right = $e;
$c->right = $f;

print_r($a);
/*
BinaryTree1 Object
(
    [value] => 1
    [left] => BinaryTree1 Object
        (
            [value] => 2
            [left] => BinaryTree1 Object
                (
                    [value] => 4
                    [left] =>
                    [right] =>
                )

            [right] => BinaryTree1 Object
                (
                    [value] => 5
                    [left] =>
                    [right] =>
                )

        )

    [right] => BinaryTree1 Object
        (
            [value] => 3
            [left] =>
            [right] => BinaryTree1 Object
                (
                    [value] => 6
                    [left] =>
                    [right] =>
                )

        )

)
*/

echo "前序遍历:";
preorder($a); //1 2 4 5 3 6
echo "\n";

echo "中序遍历:";
inorder($a);//4 2 5 1 3 6
echo "\n";

echo "后序遍历:";
tailorder($a);//4 5 2 6 3 1
echo "\n";